#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
    {
        sort(candidates.begin(), candidates.end());
        _combinationSum(candidates, 0, target);
        return _ans;
    }

private:
    bool _combinationSum(const vector<int>& candidates, int cur, int target)
    {
        if (target == 0)
        {
            _ans.push_back(_v);
            return false;
        }
        else if (target < 0)
        {
            return false;
        }

        for (int i = cur; i < candidates.size(); ++i)
        {
            if (i == cur || candidates[i - 1] != candidates[i])
            {
                _v.push_back(candidates[i]);
                bool ret = _combinationSum(candidates, i + 1, target - candidates[i]);
                _v.pop_back();

                if (!ret)
                {
                    break;
                }
            }
        }

        return true;
    }

private:
    vector<int> _v;
    vector<vector<int>> _ans;
};